/*
 * @Author: szx
 * @Date: 2021-11-23 16:55:15
 * @LastEditTime: 2021-11-23 18:23:23
 * @Description:
 * @FilePath: \leetcode\1-99\5\5.js
 */
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    let n = s.length;
    if (n < 2) return s;
    let maxLen = 1;
    let begin = 0;
    const dp =new Array(n).fill(false).map(() => new Array(n).fill(false));
    for (let i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    for (let L = 2; L <= n; L++) {
        for (let i = 0; i < n; i++) {
            let j = L + i - 1;
            if (j >= n) break;
            if (s[i] != s[j]) {
                dp[i][j] = false;
            } else {
                if (j - i < 3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1;
                begin = i;
            }
        }
    }
    return s.substring(begin, begin + maxLen);
};

var longestPalindrome = function (s) {
    const n = s.length;
    const expand = function (left, right) {
        while (left >= 0 && right < n && s[left] == s[right]) {
            --left;
            ++right;
        }
        // console.log(left);
        return [left + 1, right - 1];
    };
    let end = 0,
        start = 0;
    for (let i = 0; i < n; i++) {
        let arr = expand(i, i);
        let left = arr[0];
        let right = arr[1];
        if (right - left > end - start) {
            end = right;
            start = left;
        }
        arr = expand(i, i + 1);
        left = arr[0];
        right = arr[1];
        if (right - left > end - start) {
            end = right;
            start = left;
        }
    }
    return s.substring(start, end + 1);
};
console.log(longestPalindrome('ac'));
